package algorthm.systemTraning.dynamicPlanning;


import com.sun.deploy.util.StringUtils;

/**
 * @className: ZeroOneBag
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/3/21 14:29
 */
public class ZeroOneBag {
    public static void main(String[] args) {

//        int[] weight = {1, 2, 3, 9, 10};
//        int[] value = {11, 21, 8, 9, 10};
//        int bagWeight = 20;

        int[] weight = {1, 2, 3, 9 , 7, 10};
        int[] value = {11, 21, 8, 9 , 1 , 10};
        int bagWeight = 20;
//        int maxValue = process(weight , value , 0 , bagWeight);
//        System.out.println(maxValue);

        System.out.println(process(weight, value, 0, bagWeight));
        System.out.println(process3(weight, value, 0, bagWeight));
        System.out.println(process4(weight, value, 0, bagWeight));
        System.out.println(processWithDp(weight , value , bagWeight));
    }
    public static int processWithDp(int[] w , int[] v , int bag){
        int[][] dp = new int[w.length+1][bag+1];
//        if(w[w.length-1] <= bag){
//            dp[w.length-1][w[w.length-1]] = v[w.length - 1];
//        }
        int p1 = 0 ;
        int p2 = 0 ;
        for(int index = w.length - 1 ; index >=0  ; index--){
            for(int rest = 0 ; rest <= bag ; rest++){
                 p1 = dp[index+1][rest];
                 p2 = 0 ;
                 if(rest >= w[index]){
                     p2 = dp[index+1][rest - w[index]] + v[index];
                 }
                 dp[index][rest] =  Math.max(p1 , p2);
            }

        }
//        print(dp);
        return dp[0][bag] ;
    }
    public static void print(int[][] dp){
        for(int i = 0 ; i < dp.length ; i++){
            for(int j = 0 ; j < dp[0].length ; j++){
                System.out.print(pad(dp[i][j] , 3) + " ");
            }
            System.out.println();
        }
    }
    public static String pad(int num , int leng){
        String s = String.valueOf(num);
        StringBuilder sb = new StringBuilder();

        for(int i = 0 ; i < leng - s.length() ; i++){
            sb.append("0");
        }
        return sb.append(num).toString();
    }
    public static int process(int[] weight, int[] value, int startIdx, int bagWeight) {
        if (startIdx == weight.length - 1) {
            return (weight[startIdx] <= bagWeight ? value[startIdx] : 0);
        }
        if (bagWeight == 0) {
            return 0;
        }
        // 不将 startIdx 的物品放入背包
        int v1 = process(weight, value, startIdx + 1, bagWeight);
        int v2 = 0;
        if (bagWeight >= weight[startIdx]) {
            v2 = process(weight, value, startIdx + 1, bagWeight - weight[startIdx])
                    + value[startIdx];
        }

        return Math.max(v2, v1);
    }

    public static int process3(int[] w, int[] v, int index, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
        int p1 = process3(w, v, index + 1, rest);
        int p2 = 0;
        int next = process3(w, v, index + 1, rest - w[index]);
        if (next != -1) {
            p2 = v[index] + next;
        }
        return Math.max(p1, p2);
    }

    public static int process4(int[] weight, int[] value , int startIdx ,int bagWeight) {
        if(bagWeight < 0){
            return -1 ;
        }
        if(startIdx == weight.length){
            return 0 ;
        }
//        if(bagWeight == 0){
//            return 0;
//        }
        // 不要 startIdx 代表的物品
        int p1 = process4(weight , value , startIdx + 1 , bagWeight);
        int p2 = process4(weight , value , startIdx + 1 , bagWeight - weight[startIdx]);
        if(p2 < 0){
            return p1;
        }else{
            p2 = value[startIdx] + p2;
        }
//        int p2 = 0 ;
//        if(-1 != next){
//            p2 = value[startIdx] + next;
//        }
        return Math.max(p1 , p2);
    }


}